package com.hcj.springcloud.tree;

import lombok.extern.slf4j.Slf4j;

/**
 * 堆排序：（时间复杂度O= nlog(n)）
 * a.将无需序列构建成一个堆，根据升序降序需求选择大顶堆或小顶堆;
 * b.将堆顶元素与末尾元素交换，将最大元素"沉"到数组末端;
 * c.重新调整结构，使其满足堆定义，然后继续交换堆顶元素与当前末尾元素，反复执行调整+交换步骤，直到整个序列有序
 *
 * @author huangcj
 * @date 2021-04-12 16:09
 */
@Slf4j
public class HeapSort {
    /**
     * 交换函数
     */
    public static void swap(int[] arr, int a, int b) {
        int temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }

    /**
     * 递归调整堆:
     * 从左到右，从上到下调整
     */
    public static void heapify(int[] arr, int i, int length) {
        int left_idx = i * 2 + 1;
        int right_idx = i * 2 + 2;
        int largest = i;

        // 左子树 > 该节点
        if (left_idx < length && arr[left_idx] > arr[largest]) {
            largest = left_idx;
        }

        // 右子树 > 该节点
        if (right_idx < length && arr[right_idx] > arr[largest]) {
            largest = right_idx;
        }

        if (largest != i) {
            swap(arr, i, largest);
            heapify(arr, largest, length);
        }
    }


    /**
     * 构建大顶堆
     */
    public static void buildMaxHeap(int[] arr, int len) {
        for (int i = (arr.length - 1) / 2; i >= 0; i--) {
            heapify(arr, i, len);
        }
    }

    /**
     * 堆排序
     */
    public static int[] heapSort(int[] arr) {
        int len = arr.length;
        buildMaxHeap(arr, len);
        for (int i = len - 1; i > 0; i--) {
            // 交换最大的元素和最小的元素
            swap(arr, 0, i);
            // 自减
            len--;
            heapify(arr, 0, len);
        }
        return arr;
    }

    public static void main(String[] args) {
        int[] arr = new int[]{4, 6, 8, 5, 9};
        log.debug("堆排序前 arr = {}", arr);
        heapSort(arr);
        log.debug("堆排序后 arr = {}", arr);
    }
}
